package kyssion.leetcode.num51_100;

import kyssion.leetcode.util.TreeNode;

public class code99_恢复二叉搜索树 {

    public static void main(String[] args) {
//        TreeNode treeNode = TreeNode.create(
//                new int[]{
//                        1, 3, -1, -1, 2
//                }
//        );
        TreeNode treeNode = TreeNode.create(
                new int[]{
                        68, 41, -1, -85, -1, -73, -49, -98, -1, -1, -1, -124
                }
        );
        new code99_恢复二叉搜索树().recoverTree(treeNode);
        System.out.println();
    }

    int index = 0;
    private TreeNode leftItem = null;
    private boolean x = false;

    public void recoverTree(TreeNode root) {
        TreeNode[] errArr = new TreeNode[2];
        index = 0;
        leftItem = null;
        x = false;
        ans(root, errArr);
        if (index == 0) {
            return;
        }
        index = index == 1 ? index + 1 : index;
        int a = errArr[0].val;
        errArr[0].val = errArr[1].val;
        errArr[1].val = a;
    }

    private void ans(TreeNode root, TreeNode[] errArr) {
        if (root == null || index == 2) {
            return;
        }
        ans(root.left, errArr);
        if (leftItem != null) {
            if (root.val < leftItem.val) {
                if (index == 0) {
                    errArr[index++] = leftItem;
                    errArr[index] = root;
                    x = true;
                } else {
                    errArr[index++] = root;
                    x = false;
                }
            } else {
                if (x) {
                    if (root.val > errArr[0].val) {
                        errArr[index++] = leftItem;
                        return;
                    }
                }
                x = false;
            }
        }
        leftItem = root;
        ans(root.right, errArr);
    }

    private void ans2(TreeNode root, TreeNode[] errArr) {
        if (root == null || index == 2) {
            return;
        }
        ans(root.left, errArr);
        if (leftItem != null) {
            if (root.val < leftItem.val) {
                if (index == 0) {
                    errArr[index++] = leftItem;
                    errArr[index] = root;
                } else {
                    errArr[index++] = root;
                }
            }
        }
        leftItem = root;
        ans(root.right, errArr);
    }

    TreeNode t1,t2,pre;
    public void recoverTree2(TreeNode root) {

        inorder(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
    }

    private void inorder(TreeNode root) {
        if(root == null) return;
        inorder(root.left);
        if(pre != null && pre.val >= root.val) {
            if(t1 == null) t1= pre;
            t2 =root;
        }
        pre = root;
        inorder(root.right);
    }
}
